『(理論)12 計算モデルの基礎理論』
https://gyazo.com/f4a8e54d0c3226b1bfdc45d58d64c4a2
各章が各モデルについてになっている
めっちゃ良書
ただ、各計算モデルについて詳しく知りたければ個々の本を読んだほうがいい
ページ数的に
計算モデルの概要を掴み、語彙を増やすにはめっちゃ良い本
4章のラムダ計算はめちゃめちゃ詳しい
読んだ2019/12/16
計算機の基礎の誕生
計算機械を構築しようという試みと
計算の可能性と限界を知ろうとする試みが
互いに影響を及ぼしあって構築されてきた
その後の第二次世界大戦によって、計算機の構築も本格的になった
プログラムを計算機の記憶内に内蔵できるようになったのが計算機の発展に寄与した
実用的には扱いづらいし、実際の計算機ともかけ離れたもの
無限のテープとか言ってるしなmrsekut.icon
なので、もっと実際の計算機に近づけたものがRASPなど 読んだ2019/12/17
この本の合成$ \circの書き方が一般のものと順序が逆だなmrsekut.icon
p.39
$ f(x_1,\cdots,x_n)は、定義された引数に対しては結果が求まり停止する
定義されていない引数に対しては停止しない
$ \mathcal{L}との関連性がわからんが？mrsekut.icon
引数が$ \mathcal{L}の中身なんか？
数値関数
number theoretic function
$ \mathbb{N}^n\rightarrow\mathbb{N}な関数
$ n\in\mathbb{N}
この本特有の言葉なのかどうかは知らんmrsekut.icon
表記の意味
個数を特定しない変数の並び
$ \vec{x}:=x_1,\cdots,x_k
一応読んだ2020/1/2
最後の方の累積帰納あたりの読み方が雑かったmrsekut.icon 4章: 関数モデル
本書で使われる記号の意味
$ =は簡約の過程で得られる全ての項が同じ概念を表していることを示す
$ \twoheadrightarrowは、複数回の簡約を表す
$ \xrightarrow{\ast}_\betaとかのほうがわかりやすい気もするなmrsekut.icon
記号
p.77
要するに、木の中からある一つの節を定めたときに、それ自身とその全ての子のことを木領域と呼んでる
たぶんmrsekut.icon
以下を満たす$ \mathbb{N}_+^\astの部分集合
$ \{v\in\mathbb{N}_+^\ast|\exist w\in\mathbb{N}_+^\ast,u=v\cdot w,u\in D\}\subseteq D
$ \forall u\in Dに対して、
$ \forall i\in\mathbb{N}_+[u\cdot i\in D\Rightarrow\forall j\in\{1,\cdots,i\},u\cdot j\in D]
論理式自体は意味を持たず、解釈を与えた時に初めて意味を持つ
証明についてとか
未読
6章: 書換えモデル
未読
未読